import java.util.*;

/**
 * 题目：跳格子游戏（最多购买宝石数目）
 * 
 * 题目描述：
 * 小明和朋友在玩跳格子游戏。每个格子都有一个特定的分数。
 * 小明从score[0]开始，需要跳到最后一个格子score[n-1]。
 * 小明每次跳跃的最大步长为k。
 * 请返回小明能获得的最大总分数。
 * 
 * 输入描述：
 * 第一行输入总的格子数量n。
 * 第二行输入每个格子的分数score[]。
 * 第三行输入最大跳的步长k。
 * 
 * 输出描述：
 * 输出一个整数，表示小明能获得的最大总分数。
 * 
 * 备注：
 * - 格子总数n和跳跃步长k的范围：[1, 100000]
 * - 每个格子的分数范围：[-10000, 10000]
 * 
 * 示例1：
 * 输入：
 * 6
 * 1 -1 -6 7 -1 7 7
 * 2
 * 输出：
 * 14
 * 
 * 解题思路：
 * 这是一个动态规划问题，需要找到从起点到终点的最大分数路径。
 * 
 * 算法分析：
 * - 时间复杂度：O(n * k) 对于基本DP
 * - 空间复杂度：O(n)
 * - 算法类型：动态规划，最优化问题
 */
public class MaximumScoreJumping {
    
    /**
     * 方法1：动态规划法（推荐使用）
     * 使用动态规划求解最大分数路径
     * 
     * 算法思路：
     * 1. dp[i]表示到达位置i能获得的最大分数
     * 2. dp[i] = score[i] + max(dp[i-k], dp[i-k+1], ..., dp[i-1])
     * 3. 返回dp[n-1]
     * 
     * 时间复杂度：O(n * k)
     * 空间复杂度：O(n)
     */
    public static int maxScore1(int[] score, int k) {
        int n = score.length;
        int[] dp = new int[n];
        dp[0] = score[0];
        
        for (int i = 1; i < n; i++) {
            int maxPrev = Integer.MIN_VALUE;
            // 从前面k个位置中选择最大值
            for (int j = Math.max(0, i - k); j < i; j++) {
                maxPrev = Math.max(maxPrev, dp[j]);
            }
            dp[i] = score[i] + maxPrev;
        }
        
        return dp[n - 1];
    }
    
    /**
     * 方法2：记忆化递归法
     * 使用递归和记忆化求解
     * 
     * 算法思路：
     * 1. 使用递归函数计算从位置i到终点的最大分数
     * 2. 使用记忆化数组避免重复计算
     * 3. 递归终止条件：到达终点
     * 
     * 时间复杂度：O(n * k)
     * 空间复杂度：O(n)
     */
    public static int maxScore2(int[] score, int k) {
        int n = score.length;
        int[] memo = new int[n];
        Arrays.fill(memo, Integer.MIN_VALUE);
        
        return dfs(score, 0, k, memo);
    }
    
    private static int dfs(int[] score, int pos, int k, int[] memo) {
        if (pos >= score.length) return Integer.MIN_VALUE;
        if (pos == score.length - 1) return score[pos];
        if (memo[pos] != Integer.MIN_VALUE) return memo[pos];
        
        int maxScore = Integer.MIN_VALUE;
        for (int i = 1; i <= k && pos + i < score.length; i++) {
            int nextScore = dfs(score, pos + i, k, memo);
            if (nextScore != Integer.MIN_VALUE) {
                maxScore = Math.max(maxScore, score[pos] + nextScore);
            }
        }
        
        memo[pos] = maxScore;
        return maxScore;
    }
    
    /**
     * 方法3：滑动窗口优化法
     * 使用滑动窗口优化动态规划
     * 
     * 算法思路：
     * 1. 使用双端队列维护滑动窗口内的最大值
     * 2. 队列中存储的是位置索引，按dp值递减排列
     * 3. 每次移动窗口时更新队列
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int maxScore3(int[] score, int k) {
        int n = score.length;
        int[] dp = new int[n];
        dp[0] = score[0];
        
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(0);
        
        for (int i = 1; i < n; i++) {
            // 移除超出窗口范围的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            
            // 计算当前位置的最大分数
            if (!deque.isEmpty()) {
                dp[i] = score[i] + dp[deque.peekFirst()];
            } else {
                dp[i] = score[i];
            }
            
            // 维护单调递减队列
            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
                deque.pollLast();
            }
            deque.offer(i);
        }
        
        return dp[n - 1];
    }
    
    /**
     * 方法4：单调队列优化法
     * 使用单调队列进一步优化
     * 
     * 算法思路：
     * 1. 使用单调递减队列维护窗口内的最大值
     * 2. 队列中存储位置索引，保证dp值单调递减
     * 3. 每次只需要取队首元素作为最大值
     * 
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public static int maxScore4(int[] score, int k) {
        int n = score.length;
        int[] dp = new int[n];
        dp[0] = score[0];
        
        // 单调递减队列，存储位置索引
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(0);
        
        for (int i = 1; i < n; i++) {
            // 移除超出窗口范围的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            
            // 当前位置的最大分数
            dp[i] = score[i] + (deque.isEmpty() ? 0 : dp[deque.peekFirst()]);
            
            // 维护单调递减性质
            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
                deque.pollLast();
            }
            deque.offer(i);
        }
        
        return dp[n - 1];
    }
    
    /**
     * 方法5：贪心算法法
     * 使用贪心策略选择跳跃位置
     * 
     * 算法思路：
     * 1. 在每一步中，选择能获得最大分数的跳跃
     * 2. 考虑当前分数和未来可能获得的分数
     * 3. 使用启发式方法进行选择
     * 
     * 时间复杂度：O(n * k)
     * 空间复杂度：O(1)
     */
    public static int maxScore5(int[] score, int k) {
        int n = score.length;
        int currentPos = 0;
        int totalScore = score[0];
        
        while (currentPos < n - 1) {
            int bestNextPos = currentPos + 1;
            int bestScore = Integer.MIN_VALUE;
            
            // 在可跳跃范围内选择最佳位置
            for (int i = 1; i <= k && currentPos + i < n; i++) {
                int nextPos = currentPos + i;
                int nextScore = score[nextPos];
                
                // 简单的贪心策略：选择分数最高的位置
                if (nextScore > bestScore) {
                    bestScore = nextScore;
                    bestNextPos = nextPos;
                }
            }
            
            currentPos = bestNextPos;
            totalScore += bestScore;
        }
        
        return totalScore;
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入格子数量n：");
        int n = scanner.nextInt();
        
        System.out.println("请输入每个格子的分数（空格分隔）：");
        int[] score = new int[n];
        for (int i = 0; i < n; i++) {
            score[i] = scanner.nextInt();
        }
        
        System.out.println("请输入最大跳跃步长k：");
        int k = scanner.nextInt();
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        System.out.println("方法1（动态规划法）: " + maxScore1(score, k));
        System.out.println("方法2（记忆化递归法）: " + maxScore2(score, k));
        System.out.println("方法3（滑动窗口优化法）: " + maxScore3(score, k));
        System.out.println("方法4（单调队列优化法）: " + maxScore4(score, k));
        System.out.println("方法5（贪心算法法）: " + maxScore5(score, k));
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法4（单调队列优化法），时间复杂度最优：O(n)");
        
        scanner.close();
    }
}
